package 链表;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class No142环形链表_2 {

    /**
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
     * 如果 pos 是 -1，则在该链表中没有环。
     *
     * 说明：不允许修改给定的链表。
     */

    /**
     * 不要老想着快慢指针,可以直接遍历整条链表,一遇到重复的就return
     */
    public static ListNode detectCycle(ListNode head) {

        if(head==null||head.next==null)
            return null;

        Set<ListNode> set=new HashSet<>();

        ListNode cur=head;

        while (cur!=null){

            if(!set.contains(cur))
                set.add(cur);
            else
                return cur;

            cur=cur.next;
        }

        return null;
    }

    /**
     * 快慢指针法
     * 根据一条性质,任何时刻,快指针走过的距离都是慢指针的两倍
     */
    public static ListNode detectCycleGood(ListNode head){

        if(head==null||head.next==null){
            return null;
        }

        ListNode slowNode=head;
        ListNode fastNode=head;

        do {

            slowNode = slowNode.next;
            fastNode = fastNode.next.next;

            if (fastNode==null||fastNode.next == null) {
                return null;//没有环
            }

        } while (slowNode != fastNode);

        ListNode cur=head;

        while (cur!=slowNode){
            cur=cur.next;
            slowNode=slowNode.next;
        }

        return cur;
    }

    public static void main(String[] args) {

        ListNode listNode5=new ListNode(5,null);
        ListNode listNode4=new ListNode(4,listNode5);
        ListNode listNode3=new ListNode(3,listNode4);
        ListNode listNode2=new ListNode(2,listNode3);
        ListNode listNode1=new ListNode(1,listNode2);

        listNode5.next=listNode2;

        ListNode listNode = detectCycleGood(listNode1);
        System.out.println(listNode.val);

    }

}
